Consider the scenario where a sequence of vector symbols, with each vector having K binary elements, are sent from a transmitter to a receiver through a vector intersymbol interference (ISI) channel, whose number of taps is L, subject to additive Gaussian noise. Assume the source vector symbols are independently generated with all possible values being equal probable. If the receiver is willing to minimize the probability of sequence detection error, the optimal decision is given by the maximum likelihood (ML) sequence that maximizes the log likelihood function. Finding such sequence is known as the maximum likelihood sequence detection (MLSD) problem.
Conventionally, the ML sequence is computed using the well known Viterbi algorithm (VA), whose complexity scales linearly in the sequence length, but exponentially in the source symbol vector length K, and exponentially in the number of ISI channel taps L. Such complexity can be prohibitive for systems with large KL values. Throughout the past three decades, many attempts have been made to find sequence detectors performing about the same as the VA, but less complex in terms of the scaling law in the Markov states. The main idea considered in these algorithms is to update only a selected number of routes upon the reception of each observation so that the worst case complexity of the algorithm is under control. However, a consequence of such limited search is that none of these complexity-reduction methods can guarantee the ML sequence, which is the sequence that maximizes the log likelihood function. On the other hand, if the length of the input vector sequence, N, is small, one can regard the MLSD problem as a maximum likelihood (ML) lattice decoding problem with an input symbol vector of length NK.
Consequently, ML sequence can be obtained using various versions of the sphere decoding algorithm with low average complexity, under the assumption of high signal to noise ratio (SNR). Unfortunately, due to the difficulty of handling a lattice of infinite dimension, these algorithms cannot extend directly to the situation of stream input where the length of the source sequence is practically infinity. In summary, most existing complexity reduction methods for MLSD either cannot guarantee the ML sequence, or are not suitable for stream input.